#ifndef GAMEENGINE_CORE_GRAPH_OCTREE_H
#define GAMEENGINE_CORE_GRAPH_OCTREE_H

#include <GameEngine/Core/core_settings.h>

#include <GameEngine/Geometry/Volumes/box3d.h>
#include <GameEngine/Core/Graph/octree_node.h>

#include <vector>

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

//=====================================================================

//! Class in charge of representing an octree
/*!
 *  An octree can be used to divide recursively a three-dimensional space into a set
 *  of cubes.
 *
 *  An octree is templated by two parameters: E represents the type of elements
 *  stored by the octree and T represents the level of numerical precision required
 *  for space subdivision (T would typically either be of type float or double).
 */
template <class E, class T>
class Octree {

public:
	//! Typedef used to handle indexes in the vector of octree elements
	typedef unsigned int OctreeIndex;

	//! Typedef used to handle numbers of octree elements
	typedef unsigned int ElementCount;

	//! Typedef used to handle octree nodes
	typedef OctreeNode<OctreeIndex,T> Node;

public:
	Octree(int max_depth = 3);
	Octree(const Box3d<T>& box, int max_depth = 3);
	Octree(const Octree& rhs);
	~Octree();
	Octree& operator=(const Octree& rhs);

	const std::vector<E>& elements() const;
	std::vector<E>& elements();

	bool add_element(const E& element, const Point3d<T>& location, bool unique = true);
	bool add_element(const E& element, const Box3d<T>& location, bool unique = true);
	ElementCount remove_element(const E& element);
	bool find_element(const E& element) const;

	bool simplify(ElementCount nb_elements = 10);

	//! Accessor to the main node of the octree (read only)
	/*!
	 @return A constant reference to the main node of the octree
	 */
	const Node& node() const { return node_; }

	const Node* get_node(const Point3d<T>& location) const;
	Node* get_node(const Point3d<T>& location);
	std::list< const Node* > get_nodes(const Box3d<T>& location,
		OctreeNodeItr::OctreeNodeItrType type = OctreeNodeItr::LowLevelNodes) const;
	std::list< Node* > get_nodes(const Box3d<T>& location,
		OctreeNodeItr::OctreeNodeItrType type = OctreeNodeItr::LowLevelNodes);

protected:
	static bool simplify(Node& node, ElementCount nb_elements);
	static bool subdivide(Node& node, int level);

protected:
	//! The top-level octree node
	Node node_;

	//! Elements handled by the octree
	std::vector<E> elements_;
};

//=====================================================================

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#include <GameEngine/Core/Graph/octree.hpp>

#endif
